Da bi vrednost x bila vrednost multiplikativnog inverza $a^{-1}($mod $m)$ potrebno je da važi: $x\cdot a \equiv 1($mod $m)$ ili drugačije:
$x \cdot a = z\cdot m + 1$
$x \cdot a + y \cdot m = 1$, $y = -z$
Dakle, potrebno je pronaći $NZD$ za vrednosti a i m. Ukoliko je $NZD$ različit od jedinice, traženi multiplikativni inverz ne postoji jer vrednosti nisu uzajamno proste. Ako je $NZD$ jednak jedinici, onda prošireni Euklidov algoritam pronalazi vrednosti $x$ i $y$ za koje je jednakost tačna i vrednost $x$ je upravo traženi multiplikativni inverz.
# Pomoćna funkcija, prošireni Euklidov algoritam
def ext_gcd(a, b):
if b == 0:
return (a, 1, 0)
g, x, y = ext_gcd(b, a % b)
return (g, y, x - a // b * y)
def mod_inv(a, m):
g, x, y = ext_gcd(a, m)
if g != 1:
print("Vrednosti a i m nisu uzajamno proste!")
else:
return x % m
# Multiplikativni inverz 36^-1 (mod 81) ne postoji jer vrednosti 36 i 81 nisu uzajamno proste
a = 36
m = 81
mod_inv(a, m)
# Dok multiplikativni inverz 36^-1 (mod 83) postoji
a = 36
m = 83
mod_inv(a, m)
# Provera
a_1 = mod_inv(a, m) % m
print(f'{a}^-1(mod {m}) = {a_1}')
print(f'{a} * {a_1} = {a * a_1 % m} (mod {m})')